package leetcode101.binary_search;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code3
 * @Description 81. Search in Rotated Sorted Array II
 * <p>
 * There is an integer array nums sorted in non-decreasing order (not necessarily with distinct values).
 * <p>
 * Before being passed to your function, nums is rotated at an unknown pivot index k (0 <= k < nums.length)
 * such that the resulting array is
 * [nums[k], nums[k+1], ..., nums[n-1], nums[0], nums[1], ..., nums[k-1]] (0-indexed).
 * For example, [0,1,2,4,4,4,5,6,6,7] might be rotated at pivot index 5 and become [4,5,6,6,7,0,1,2,4,4].
 * <p>
 * Given the array nums after the rotation and an integer target,
 * return true if target is in nums, or false if it is not in nums.
 *
 * Example 1:
 * <p>
 * Input: nums = [2,5,6,0,0,1,2], target = 0
 * Output: true
 * Example 2:
 *
 * Input: nums = [2,5,6,0,0,1,2], target = 3
 * Output: false
 *
 * Constraints:
 *
 * 1 <= nums.length <= 5000
 * -104 <= nums[i] <= 104
 * nums is guaranteed to be rotated at some pivot.
 * -104 <= target <= 104
 *
 * Follow up: This problem is the same as Search in Rotated Sorted Array, where nums may contain duplicates.
 * Would this affect the runtime complexity? How and why?
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-03-28 10:20
 */
public class Code3 {
    public static void main(String[] args) {
        int[] nums = new int[]{2, 5, 6, 0, 0, 1, 2};
        System.out.println(search(nums, 3));
    }

    public static boolean search(int[] nums, int target) {
        int pivot = getPivot(nums);
        return binarySearch(nums, target, 0, pivot) ||
               binarySearch(nums, target, pivot + 1, nums.length - 1);
    }

    public static int getPivot(int[] nums) {
        for (int i = 0; i < nums.length - 1; i++) {
            if (nums[i] > nums[i + 1]) {
                return i;
            }
        }
        return -1;
    }

    public static boolean binarySearch(int[] nums, int target, int low, int high) {
        int mid;
        while (low <= high) {
            mid = (low + high) >> 1;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[mid] < target) {
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return false;
    }

//    public static boolean search(int[] nums, int target) {
//        int low = 0, high = nums.length - 1, mid;
//        while (low <= high) {
//            mid = (low + high) >> 1;
//            if (nums[mid] == target) return true;
//            if (nums[mid] == nums[low]) low++;
//            else if (nums[mid] <= nums[high]) { // 右半边有序
//                if (target > nums[mid] && target <= nums[high]) {
//                    low = mid + 1;
//                } else {
//                    high = mid - 1;
//                }
//            } else {
//                if (target < nums[mid] && target >= nums[low]) {
//                    high = mid - 1;
//                } else {
//                    low = mid + 1;
//                }
//            }
//        }
//        return false;
//    }

}
/*
大致思路就是首先找到旋转点，然后对左右两个有序的数组进行二分查找
 */